package cn.michael.dev.data.structure.linked.list;

import cn.michael.dev.entity.ListNode;

import java.util.HashSet;

/**
 * Created by hufenggang on 2021/8/26.
 *
 * 环形链表
 */
public class Problem141 {

    /**
     * 基于哈希表实现
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> hashSet = new HashSet<>();

        while (head != null) {
            if (hashSet.contains(head)) {
                return true;
            }
            hashSet.add(head);
            head = head.next;
        }
        return false;
    }


    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode firstNode = head;
        ListNode lastNode = head.next;

        while (firstNode != lastNode) {
            if (lastNode == null || lastNode.next == null) {
                return false;
            }
            firstNode = firstNode.next;
            lastNode = lastNode.next.next;
        }

        return true;
    }
}
